🚀 The Problem

Your Mission 🎯

Reconnect $N$ planets, given as 2D coordinates, with a minimum-cost "Hyper-lane" network.

  • Goal: Connect all $N$ planets (vertices) so they are all reachable (directly or indirectly).
  • Objective: Find the network design that minimizes the **total cost**.

Analysis 🛰️

The cost of a lane (edge) is the Euclidean distance:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
  • A lane can be built between any two planets.
  • This means we have a complete (dense) graph.

The Solution ⚙️

This is a classic Minimum Spanning Tree (MST) problem.

  • Algorithm: The hint recommends Prim's Algorithm (the $O(V^2)$ version), which is perfect for dense graphs.
  • Starting Point: We will start our algorithm from Planet 0 for a consistent result.

A complete graph (left) has all possible edges. The MST (right) is the cheapest subset of edges that connects all vertices.